package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 12/7/20 4:08 PM
 *
 * https://leetcode-cn.com/problems/reverse-words-in-a-string/
 */
public class _151_翻转字符串里的单词 {

    public String reverseWords(String s) {

        if (s == null || s.length() == 0) {
            return "";
        }


        // 去除空格
        char[] cs = s.toCharArray();

        int loc = 0, cur = 0;
        boolean firstSpace = true;
        while (cur < cs.length) {

            if (cs[cur] != ' ') {

                cs[loc++] = cs[cur++];
                firstSpace = true;
            }else {

                if (firstSpace && loc > 0) {

                    firstSpace = false;
                    cs[loc++] = ' ';
                }
                cur++;
            }
        }

        int len =  firstSpace ? loc:loc-1;

        if (len == 0) {

            return "";
        }

        reversalChars(cs,0,len - 1);

        int start = 0;

        for (int i = 1; i < len; i++) {

            if (cs[i] == ' ') {

                reversalChars(cs,start,i - 1);
                start = i+1;
            }
        }

        if (start < len) {

            reversalChars(cs,start,len - 1);
        }

        return new String(cs,0,len);
    }


    private void reversalChars(char[] cs, int start, int end) {

        if (start == end) {

            return;
        }

        int left = start,right = end;

        while (left < right) {

            char tmp = cs[left];
            cs[left] = cs[right];
            cs[right] = tmp;
            left++;
            right--;
        }
    }

}
